// #include<vector>
// #include<limits>
// #include<cstddef>
// #include<iostream>
// #include<sstream>
// #include<map>
// #include<algorithm>
// #include<tuple>
// #include<unordered_map>
// #include<functional>
// #include<memory>
// #include<cstdint>
// using namespace std;

// typedef std::tuple<int,int> keyT;
// struct key_hash : public std::unary_function<keyT, std::size_t>{
//     std::size_t operator()(const keyT& k) const {
//         return std::get<0>(k) ^ std::get<1>(k);
//     }
// };
// struct key_equal : public std::binary_function<keyT, keyT, bool>{
//     bool operator()(const keyT& v0, const keyT& v1) const{
//         return std::get<0>(v0) == std::get<0>(v1) 
//             && std::get<1>(v0) == std::get<1>(v1);
//             // && std::get<2>(v0) == std::get<2>(v1)
//         // ;
//     }
// };
// typedef std::unordered_map<const keyT, std::uint64_t, key_hash, key_equal > map_t;

// enum NeiState{
//     IsB,
//     IsA,
//     Empty,
//     NeedA,
// };
// class Lonely{
// public:
//     int N;
// //不存在的个数 2^100次方
// //a旁边存在a
// //aa baa aab
//     //寻找所有A 必然旁边存在一个A
//     map_t cache;
//     std::uint64_t LoneNum(int startPos, NeiState st){
//         if(startPos >= N){
//             if(st == NeiState::NeedA) return 0;
//             return 1;
//         }
//         auto key = std::make_tuple(startPos, (int)st);
//         if(cache.find(key) != cache.end()) return cache[key];

//         //可A 可B
//         if(st == NeiState::Empty){
//             auto n1 = LoneNum(startPos+1, NeiState::NeedA); //左边为空
//             auto n2 = LoneNum(startPos+1, NeiState::IsB);
//             auto total = n1+n2;
//             cache[key] = total;
//             return total;
//         }
//         //只能选择A
//         if(st == NeiState::NeedA){
//             auto n1 = LoneNum(startPos+1, NeiState::IsA);
//             cache[key] = n1;
//             return n1;
//         }
//         //可A 可B
//         if(st == NeiState::IsB){
//             auto n1 = LoneNum(startPos+1, NeiState::NeedA);
//             auto n2 = LoneNum(startPos+1, NeiState::IsB);
//             auto total = n1+n2;
//             cache[key] = total;
//             return total;
//         }
//         //aa
//         if(st == NeiState::IsA){
//             auto n1 = LoneNum(startPos+1, NeiState::IsA);
//             auto n2 = LoneNum(startPos+1, NeiState::IsB);
//             auto total = n1+n2;
//             cache[key] = total;
//             return total;
//         }

//         return 0;
//     }
// };
// int main(int, char**) {
//     string nn;
//     getline(cin, nn);
//     auto nv = stoi(nn);
//     for(auto iv = 0; iv < nv; iv++){
//         string dv;
//         getline(cin, dv);
//         Lonely ll;
//         ll.N = stoi(dv);
//         auto r = ll.LoneNum(0, NeiState::Empty);
//         std::uint64_t total = 1;
//         auto leftN = ll.N;
//         for(auto i = 0; i < ll.N; i++){
//             total *= 2;
//             leftN--;
//             if(total >= r) break;
//         }
//         auto oldTotal = total;
//         total -= r;
//         auto needOne = 1;
//         for(auto i =0 ; i < leftN; i++){
//             needOne *= 2;
//         }
//         auto left = (needOne-1)*oldTotal + total;
//         cout << left << endl;
//     }

// }
